package 程序员面试金典;

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.Queue;

/**
 * 面试题 04.03. 特定深度节点链表
 * 给定一棵二叉树，设计一个算法，创建含有某一深度上所有节点的链表（比如，若一棵树的深度为 D，则会创建出 D 个链表）。返回一个包含所有深度的链表的数组。
 *
 *
 *
 * 示例：
 *
 * 输入：[1,2,3,4,5,null,7,8]
 *
 *         1
 *        /  \
 *       2    3
 *      / \    \
 *     4   5    7
 *    /
 *   8
 *
 * 输出：[[1],[2,3],[4,5,7],[8]]
 */
public class T04_03 {
    public ListNode[] listOfDepth(TreeNode tree) {

        int index = 0;
        if (tree == null) {
            return new ListNode[0];
        }


        ArrayList<ListNode> ans = new ArrayList<>();
        //层序遍历  使用两个队列分别存放奇数层 和偶数层的节点
        Queue<TreeNode> q1 = new LinkedList<>();
        Queue<TreeNode> q2 = new LinkedList<>();

        q1.add(tree);

        while (!q1.isEmpty() || !q2.isEmpty()) {

            ListNode preHead = new ListNode(-1);
            ListNode curr = preHead;
            if (!q1.isEmpty()) {
                while (!q1.isEmpty()) {

                    TreeNode treeNode = q1.poll();
                    ListNode next = new ListNode(treeNode.val);
                    curr.next = next;
                    curr = curr.next;
                    if (treeNode.left != null) {
                        q2.add(treeNode.left);
                    }
                    if (treeNode.right != null) {
                        q2.add(treeNode.right);
                    }

                }
                ans.add(preHead.next);
            }

            if (!q2.isEmpty()) {
                while (!q2.isEmpty()) {

                    TreeNode treeNode = q2.poll();
                    ListNode next = new ListNode(treeNode.val);
                    curr.next = next;
                    curr = curr.next;
                    if (treeNode.left != null) {
                        q1.add(treeNode.left);
                    }
                    if (treeNode.right != null) {
                        q1.add(treeNode.right);
                    }

                }
                ans.add(preHead.next);
            }

        }

        return ans.<ListNode>toArray(new ListNode[ans.size()]);
    }

    static class TreeNode {
        int val;
        TreeNode left;
        TreeNode right;

        TreeNode(int x) {
            val = x;
        }
    }

    static class ListNode {
        int val;
        ListNode next;

        ListNode(int x) {
            val = x;
        }
    }

}
